The present invention relates to a packet switching apparatus which is used in the asynchronous transfer mode (to be referred to as ATM hereafter) and a packet switching apparatus for forwarding IP (internet protocol) packets.
FIG. 14 is a block diagram of an ATM switching apparatus for switching fixed length packets (referred to as cells for ATM). The ATM switching apparatus includes ingress cards 85, a switch 86, egress cards 87, and a controller 88. An ingress card 85 contains a line terminator 851 for terminating a physical layer signal received from a transmission line 850, a UPC (Usage Parameter Control)/OAM (Operation Administration and Maintenance) unit 852 used for flow monitoring and performance monitoring, a header converter 853 for changing the label of each received cell and for giving the cell a routing header for switching. An egress card 87 is provided with an OAM unit 871, a line output unit for terminating the ATM layer and for processing a physical layer signal to output the signal to a transmission line 870. The egress card 87 may have the function to distribute signals to lower the line speed. The egress card 87 may also be provided with a shaping buffer for priority control in some cases.
Different types of ATM switch are described in xe2x80x9cBroadband ISDN and ATM Techniquesxe2x80x9d (page 101) issued in February, 1995, by The Institute of Electronics, Information and Communication Engineers. The ATM switches proposed so far have their own characteristics according to the placement of cell buffer memories. A shared buffer type ATM switch, disclosed in U.S. Pat. No. 4,910,731 or xe2x80x9cShared Buffer Type Memory Switch for ATM Switching Networkxe2x80x9d, introduced in the Transactions of IEICE BI (J72-B-1, No. 11, pp. 1062-1069, November, 1989), has a centralized buffer memory shared among all the output ports of the switch. The shared buffer type switch has been widely used because buffer sharing can reduce the amount of hardware; in other words, buffer memory utilization is highly improved compared with that of a separated buffer type memory switch.
FIG. 2 is a block diagram of a conventional ATM switch with a shared buffer. The operation of this switch will be explained as follows. Cells from all the input lines 10 (10-1 to 10-n) enter the multiplexer (MUX) 2. A route decoder 4 then selects a write address register (WA)6 (any of 6-1 to 6-n) by decoding the cell header obtained from MUX2, which indicates the destination output. The write address of a cell buffer memory 1 is obtained from a WA (any of 6-1 to 6-n) and multiplexed cells are written one by one into the cell area 1-1 in the buffer memory 1. At the same time, an idle address provided from an idle address buffer (IABF) 8 is written in the address pointer area 1-2 of the same address as the cell is written in, and it also is written in the, selected write address register (WA) 6 (any of 6-1 to 6-n) overwriting the former WA6 (any of 6-1 to 6-n) content. This address indicates the writing address of the next cell, which will be input into the output queue corresponding to the same WA6 (any of 6-1 to 6-n). When a cell is output from the switch, the reading address of the buffer memory 1 is determined by the read address register (RA) 7 (any of 7-1 to 7-n) each corresponding to the output line. An output counter 9 and an output decoder 5 specify one of the address registers (RA) 7 (any of 7-1 to 7-n) cyclically. The output cells from the buffer memory 1 are demultiplexed through a demultiplexer (DMX) 3 to the target output line 11 (any of 11-1 to 11-n). When the cell is read, the address pointer in the same address overwrites the read address register (RA) 7 (any of 7-1 to 7-n) which had indicated the reading address. The address previously contained in RA (same as the address from which the cell is read) is stored in IABF8, because this address. becomes idle and is replaced by the next address.
FIG. 3 shows the structure of an address chain corresponding to an output line, constructed by the address pointers. An address chain 20-1 corresponding to an output line 11-1 is formed between a start address stored in the read address register (RA1) 7-1 and an end address stored in the write address register (WA1) 6-1. Another address chain 20-2 corresponding to an output line 11-2 is formed between a start address stored in the read address register (RA2) 7-2 and an end address stored in the write address register (WA2) 6-2.
The operation described above shows a simple example of how to realize address chains corresponding to output lines. Each chain logically acts as a queue buffer for each output on the same memory. The above mentioned switch is easily modified to provide a priority control function by assigning a plurality of queues corresponding to multiple service classes and output lines, respectively, as disclosed in U.S. Pat. No. 4,910,731.
Furthermore, the official gazette of Japanese Patent Application No. 3-10441 has disclosed a shared buffer switch, in which, m demultiplexers are connected to input lines and m multiplexers are connected to output lines of the switch having an I/O line speed of V and a switching capacity of nxc3x97n, resulting in a switch having I/O lines speeded up to mV and a switching capacity of (n/m)xc3x97(n/m).
FIG. 4 shows a shared buffer switch with fast I/O lines, the speed of which is doubled using the method mentioned above A fast input line 12-1 is demultiplexed by a demultiplexer 13-1 to input lines 10-1 and 10-2. Both of the lines 10-1 and 10-2 are connected to a MUX 2, respectively. Each cell multiplexed by MUX 2 is stored in the shared buffer 1 by forming an address chain corresponding to each of the output lines 15-1 and 15-2. Two cells belonging to the same address chain are sequentially read from the cell buffer 1. Then, for example, the two cells bound for the same output line 15-1 are demultiplexed to lines 11-1 and 11-2, and next multiplexed to the designated output line 15-1 by a multiplexer 14-1.
The above mentioned shared buffer switches have been mainly targeted for an ATM node which switches fixed length packets called cells. To realize a large-scale IP router, the same switching architecture with fixed length packets is effective. In this regard, a variable length IP packet is chopped up into fixed length packets and they are switched by hardware at the switch core, and then segmented portions are reconstructed into the original IP packet For example, xe2x80x9cThe Tirfy Tera: A Packet Switch Corexe2x80x9d (Hot Interconnects V, Stanford University, August 1996) has proposed a crossbar switch with input buffers. This switch architecture requires scheduling of packet transfer between input ports and output ports. In this configuration, each input buffer is divided into plural queue buffers corresponding to each output port so that packets can be read from any queue buffer indicated by the scheduler, thereby reducing the throughput degradation by HOL (Head Of Line Blocking).
In the above conventional shared buffer switch, an address chain is formed for each corresponding output line. In other words, one logical queue per output port is constructed on the shared buffer memory. In this structure, the interval of updating each address chain limits the attainable line speed.
Under such the circumstances, therefore, the main object of the present invention is to provide a shared buffer switch with a fast input and output line rate.
According to the present invention, a plurality of address chains are assigned to each flow. (A flow is defined as different kinds of level, such as output port, priority class and so on). A plurality of logical queues formed by plural address chains are pipelined. Concretely, the switch of the present invention is equipped with a distributive pointer for distributing each cell flow to a plurality of address chains cyclically and a read pointer to select one of the address chains cyclically. These pointers are provided for each flow and have a task to select a chain each time in a manner to preserve the sequential order of cell flow. Consequently, with this architecture, it is possible to access another address chain of the same flow sequentially before updating one chain. As a result, the time interval of cells in each flow output from the shared buffer switch can be shortened.
Furthermore, the distributive pointer and the read pointer can be activated on demand, thereby enabling selection of fast or slow input/output lines or coexistence of fast and slow lines in the same switch.